home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / glibc108.zip / glibc108 / sysdeps / generic / memcmp.c < prev    next >
C/C++ Source or Header  |  1994-01-17  |  9KB  |  400 lines
  1. /* Copyright (C) 1991, 1993 Free Software Foundation, Inc.
  2.    Contributed by Torbjorn Granlund (tege@sics.se).
  3.  
  4. The GNU C Library is free software; you can redistribute it and/or
  5. modify it under the terms of the GNU Library General Public License as
  6. published by the Free Software Foundation; either version 2 of the
  7. License, or (at your option) any later version.
  8.  
  9. The GNU C Library is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12. Library General Public License for more details.
  13.  
  14. You should have received a copy of the GNU Library General Public
  15. License along with the GNU C Library; see the file COPYING.LIB.  If
  16. not, write to the Free Software Foundation, Inc., 675 Mass Ave,
  17. Cambridge, MA 02139, USA.  */
  18.  
  19. #ifdef HAVE_CONFIG_H
  20. #include "config.h"
  21. #endif
  22.  
  23. #undef    __ptr_t
  24. #if defined (__cplusplus) || (defined (__STDC__) && __STDC__)
  25. #define    __ptr_t    void *
  26. #else /* Not C++ or ANSI C.  */
  27. #undef    const
  28. #define    const
  29. #define    __ptr_t    char *
  30. #endif /* C++ or ANSI C.  */
  31.  
  32. #if defined (HAVE_STRING_H) || defined (_LIBC)
  33. #include <string.h>
  34. #endif
  35.  
  36. #ifdef _LIBC
  37.  
  38. #include <memcopy.h>
  39.  
  40. #else    /* Not in the GNU C library.  */
  41.  
  42. #include <sys/types.h>
  43.  
  44. /* Type to use for aligned memory operations.
  45.    This should normally be the biggest type supported by a single load
  46.    and store.  Must be an unsigned type.  */
  47. #define    op_t    unsigned long int
  48. #define OPSIZ    (sizeof(op_t))
  49.  
  50. /* Threshold value for when to enter the unrolled loops.  */
  51. #define    OP_T_THRES    16
  52.  
  53. /* Type to use for unaligned operations.  */
  54. typedef unsigned char byte;
  55.  
  56. #ifndef WORDS_BIGENDIAN
  57. #define MERGE(w0, sh_1, w1, sh_2) (((w0) >> (sh_1)) | ((w1) << (sh_2)))
  58. #else
  59. #define MERGE(w0, sh_1, w1, sh_2) (((w0) << (sh_1)) | ((w1) >> (sh_2)))
  60. #endif
  61.  
  62. #endif    /* In the GNU C library.  */
  63.  
  64.  
  65. /* BE VERY CAREFUL IF YOU CHANGE THIS CODE!  */
  66.  
  67. /* The strategy of this memcmp is:
  68.  
  69.    1. Compare bytes until one of the block pointers is aligned.
  70.  
  71.    2. Compare using memcmp_common_alignment or
  72.       memcmp_not_common_alignment, regarding the alignment of the other
  73.       block after the initial byte operations.  The maximum number of
  74.       full words (of type op_t) are compared in this way.
  75.  
  76.    3. Compare the few remaining bytes.  */
  77.  
  78. #ifndef WORDS_BIGENDIAN
  79. /* memcmp_bytes -- Compare A and B bytewise in the byte order of the machine.
  80.    A and B are known to be different.
  81.    This is needed only on little-endian machines.  */
  82. #ifdef  __GNUC__
  83. __inline
  84. #endif
  85. static int
  86. memcmp_bytes (a, b)
  87.      op_t a, b;
  88. {
  89.   long int srcp1 = (long int) &a;
  90.   long int srcp2 = (long int) &b;
  91.   op_t a0, b0;
  92.  
  93.   do
  94.     {
  95.       a0 = ((byte *) srcp1)[0];
  96.       b0 = ((byte *) srcp2)[0];
  97.       srcp1 += 1;
  98.       srcp2 += 1;
  99.     }
  100.   while (a0 == b0);
  101.   return a0 - b0;
  102. }
  103. #endif
  104.  
  105. /* memcmp_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN `op_t'
  106.    objects (not LEN bytes!).  Both SRCP1 and SRCP2 should be aligned for
  107.    memory operations on `op_t's.  */
  108. #ifdef    __GNUC__
  109. __inline
  110. #endif
  111. static int
  112. memcmp_common_alignment (srcp1, srcp2, len)
  113.      long int srcp1;
  114.      long int srcp2;
  115.      size_t len;
  116. {
  117.   op_t a0, a1;
  118.   op_t b0, b1;
  119.  
  120.   switch (len % 4)
  121.     {
  122.     case 2:
  123.       a0 = ((op_t *) srcp1)[0];
  124.       b0 = ((op_t *) srcp2)[0];
  125.       srcp1 -= 2 * OPSIZ;
  126.       srcp2 -= 2 * OPSIZ;
  127.       len += 2;
  128.       goto do1;
  129.     case 3:
  130.       a1 = ((op_t *) srcp1)[0];
  131.       b1 = ((op_t *) srcp2)[0];
  132.       srcp1 -= OPSIZ;
  133.       srcp2 -= OPSIZ;
  134.       len += 1;
  135.       goto do2;
  136.     case 0:
  137.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  138.     return 0;
  139.       a0 = ((op_t *) srcp1)[0];
  140.       b0 = ((op_t *) srcp2)[0];
  141.       goto do3;
  142.     case 1:
  143.       a1 = ((op_t *) srcp1)[0];
  144.       b1 = ((op_t *) srcp2)[0];
  145.       srcp1 += OPSIZ;
  146.       srcp2 += OPSIZ;
  147.       len -= 1;
  148.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  149.     goto do0;
  150.       /* Fall through.  */
  151.     }
  152.  
  153.   do
  154.     {
  155.       a0 = ((op_t *) srcp1)[0];
  156.       b0 = ((op_t *) srcp2)[0];
  157.       if (a1 != b1)
  158. #ifdef WORDS_BIGENDIAN
  159.     return a1 > b1 ? 1 : -1;
  160. #else
  161.     return memcmp_bytes (a1, b1);
  162. #endif
  163.  
  164.     do3:
  165.       a1 = ((op_t *) srcp1)[1];
  166.       b1 = ((op_t *) srcp2)[1];
  167.       if (a0 != b0)
  168. #ifdef WORDS_BIGENDIAN
  169.     return a0 > b0 ? 1 : -1;
  170. #else
  171.     return memcmp_bytes (a0, b0);
  172. #endif
  173.  
  174.     do2:
  175.       a0 = ((op_t *) srcp1)[2];
  176.       b0 = ((op_t *) srcp2)[2];
  177.       if (a1 != b1)
  178. #ifdef WORDS_BIGENDIAN
  179.     return a1 > b1 ? 1 : -1;
  180. #else
  181.     return memcmp_bytes (a1, b1);
  182. #endif
  183.  
  184.     do1:
  185.       a1 = ((op_t *) srcp1)[3];
  186.       b1 = ((op_t *) srcp2)[3];
  187.       if (a0 != b0)
  188. #ifdef WORDS_BIGENDIAN
  189.     return a0 > b0 ? 1 : -1;
  190. #else
  191.     return memcmp_bytes (a0, b0);
  192. #endif
  193.  
  194.       srcp1 += 4 * OPSIZ;
  195.       srcp2 += 4 * OPSIZ;
  196.       len -= 4;
  197.     }
  198.   while (len != 0);
  199.  
  200.   /* This is the right position for do0.  Please don't move
  201.      it into the loop.  */
  202.  do0:
  203.   if (a1 != b1)
  204. #ifdef WORDS_BIGENDIAN
  205.     return a1 > b1 ? 1 : -1;
  206. #else
  207.     return memcmp_bytes (a1, b1);
  208. #endif
  209.   return 0;
  210. }
  211.  
  212. /* memcmp_not_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN
  213.    `op_t' objects (not LEN bytes!).  SRCP2 should be aligned for memory
  214.    operations on `op_t', but SRCP1 *should be unaligned*.  */
  215. #ifdef    __GNUC__
  216. __inline
  217. #endif
  218. static int
  219. memcmp_not_common_alignment (srcp1, srcp2, len)
  220.      long int srcp1;
  221.      long int srcp2;
  222.      size_t len;
  223. {
  224.   op_t a0, a1, a2, a3;
  225.   op_t b0, b1, b2, b3;
  226.   op_t x;
  227.   int shl, shr;
  228.  
  229.   /* Calculate how to shift a word read at the memory operation
  230.      aligned srcp1 to make it aligned for comparison.  */
  231.  
  232.   shl = 8 * (srcp1 % OPSIZ);
  233.   shr = 8 * OPSIZ - shl;
  234.  
  235.   /* Make SRCP1 aligned by rounding it down to the beginning of the `op_t'
  236.      it points in the middle of.  */
  237.   srcp1 &= -OPSIZ;
  238.  
  239.   switch (len % 4)
  240.     {
  241.     case 2:
  242.       a1 = ((op_t *) srcp1)[0];
  243.       a2 = ((op_t *) srcp1)[1];
  244.       b2 = ((op_t *) srcp2)[0];
  245.       srcp1 -= 1 * OPSIZ;
  246.       srcp2 -= 2 * OPSIZ;
  247.       len += 2;
  248.       goto do1;
  249.     case 3:
  250.       a0 = ((op_t *) srcp1)[0];
  251.       a1 = ((op_t *) srcp1)[1];
  252.       b1 = ((op_t *) srcp2)[0];
  253.       srcp2 -= 1 * OPSIZ;
  254.       len += 1;
  255.       goto do2;
  256.     case 0:
  257.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  258.     return 0;
  259.       a3 = ((op_t *) srcp1)[0];
  260.       a0 = ((op_t *) srcp1)[1];
  261.       b0 = ((op_t *) srcp2)[0];
  262.       srcp1 += 1 * OPSIZ;
  263.       goto do3;
  264.     case 1:
  265.       a2 = ((op_t *) srcp1)[0];
  266.       a3 = ((op_t *) srcp1)[1];
  267.       b3 = ((op_t *) srcp2)[0];
  268.       srcp1 += 2 * OPSIZ;
  269.       srcp2 += 1 * OPSIZ;
  270.       len -= 1;
  271.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  272.     goto do0;
  273.       /* Fall through.  */
  274.     }
  275.  
  276.   do
  277.     {
  278.       a0 = ((op_t *) srcp1)[0];
  279.       b0 = ((op_t *) srcp2)[0];
  280.       x = MERGE(a2, shl, a3, shr);
  281.       if (x != b3)
  282. #ifdef WORDS_BIGENDIAN
  283.     return x > b3 ? 1 : -1;
  284. #else
  285.     return memcmp_bytes (x, b3);
  286. #endif
  287.  
  288.     do3:
  289.       a1 = ((op_t *) srcp1)[1];
  290.       b1 = ((op_t *) srcp2)[1];
  291.       x = MERGE(a3, shl, a0, shr);
  292.       if (x != b0)
  293. #ifdef WORDS_BIGENDIAN
  294.     return x > b0 ? 1 : -1;
  295. #else
  296.     return memcmp_bytes (x, b0);
  297. #endif
  298.  
  299.     do2:
  300.       a2 = ((op_t *) srcp1)[2];
  301.       b2 = ((op_t *) srcp2)[2];
  302.       x = MERGE(a0, shl, a1, shr);
  303.       if (x != b1)
  304. #ifdef WORDS_BIGENDIAN
  305.     return x > b1 ? 1 : -1;
  306. #else
  307.     return memcmp_bytes (x, b1);
  308. #endif
  309.  
  310.     do1:
  311.       a3 = ((op_t *) srcp1)[3];
  312.       b3 = ((op_t *) srcp2)[3];
  313.       x = MERGE(a1, shl, a2, shr);
  314.       if (x != b2)
  315. #ifdef WORDS_BIGENDIAN
  316.     return x > b2 ? 1 : -1;
  317. #else
  318.     return memcmp_bytes (x, b2);
  319. #endif
  320.  
  321.       srcp1 += 4 * OPSIZ;
  322.       srcp2 += 4 * OPSIZ;
  323.       len -= 4;
  324.     }
  325.   while (len != 0);
  326.  
  327.   /* This is the right position for do0.  Please don't move
  328.      it into the loop.  */
  329.  do0:
  330.   x = MERGE(a2, shl, a3, shr);
  331.   if (x != b3)
  332. #ifdef WORDS_BIGENDIAN
  333.     return x > b3 ? 1 : -1;
  334. #else
  335.     return memcmp_bytes (x, b3);
  336. #endif
  337.   return 0;
  338. }
  339.  
  340. int
  341. memcmp (s1, s2, len)
  342.      const __ptr_t s1;
  343.      const __ptr_t s2;
  344.      size_t len;
  345. {
  346.   op_t a0;
  347.   op_t b0;
  348.   long int srcp1 = (long int) s1;
  349.   long int srcp2 = (long int) s2;
  350.   op_t res;
  351.  
  352.   if (len >= OP_T_THRES)
  353.     {
  354.       /* There are at least some bytes to compare.  No need to test
  355.      for LEN == 0 in this alignment loop.  */
  356.       while (srcp2 % OPSIZ != 0)
  357.     {
  358.       a0 = ((byte *) srcp1)[0];
  359.       b0 = ((byte *) srcp2)[0];
  360.       srcp1 += 1;
  361.       srcp2 += 1;
  362.       res = a0 - b0;
  363.       if (res != 0)
  364.         return res;
  365.       len -= 1;
  366.     }
  367.  
  368.       /* SRCP2 is now aligned for memory operations on `op_t'.
  369.      SRCP1 alignment determines if we can do a simple,
  370.      aligned compare or need to shuffle bits.  */
  371.  
  372.       if (srcp1 % OPSIZ == 0)
  373.     res = memcmp_common_alignment (srcp1, srcp2, len / OPSIZ);
  374.       else
  375.     res = memcmp_not_common_alignment (srcp1, srcp2, len / OPSIZ);
  376.       if (res != 0)
  377.     return res;
  378.  
  379.       /* Number of bytes remaining in the interval [0..OPSIZ-1].  */
  380.       srcp1 += len & -OPSIZ;
  381.       srcp2 += len & -OPSIZ;
  382.       len %= OPSIZ;
  383.     }
  384.  
  385.   /* There are just a few bytes to compare.  Use byte memory operations.  */
  386.   while (len != 0)
  387.     {
  388.       a0 = ((byte *) srcp1)[0];
  389.       b0 = ((byte *) srcp2)[0];
  390.       srcp1 += 1;
  391.       srcp2 += 1;
  392.       res = a0 - b0;
  393.       if (res != 0)
  394.     return res;
  395.       len -= 1;
  396.     }
  397.  
  398.   return 0;
  399. }
  400.